// 思路：1. 首先构造大顶堆，从最后一个非叶子节点开始，直到首节点进行heapify堆化
// 2. 构成大顶堆后，将首节点和最后一个元素交换，然后将首节点的元素堆化
// 3. 不断缩小区间重复这个过程
// 时间复杂度：Onlogn
// 空间复杂度：O1
// 稳定性：不稳定
// 适用场景: 大数据量，部分排序，优先队列
function maxHeapSort(arr) {
    for (let i = Math.floor((arr.length - 2) / 2); i >= 0; i--) {
        heapify(arr, i, arr.length - 1)
    }
    for (let i = 0; i < arr.length; i++) {
        [arr[0], arr[arr.length - 1 - i]] = [arr[arr.length - 1 - i], arr[0]];
        // 已经确定一个位置，这里的end要多减一个1
        heapify(arr, 0, arr.length - 2 - i)
    }
    return arr
}

function heapify(arr, start, end) {
    let left = 2 * start + 1
    let right = left + 1
    while (left <= end) {
        let idx = start
        if (arr[left] > arr[idx]) {
            idx = left
        }
        if (right <= end && arr[right] > arr[idx]) {
            idx = right
        }
        if (idx === start) {
            break
        }
        [arr[idx], arr[start]] = [arr[start], arr[idx]];
        left = 2 * idx + 1;
        right = left + 1;
    }
}

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(maxHeapSort(arr))